package com.learn.algorithm;

import java.util.Arrays;

/**
 * 求连续子数组的最大和
 * 描述:
 * 给定一个数组 array[1, 4, -5, 9, 8, 3, -6]，在这个数字中有多个子数组，子数组和最大的应该是：[9, 8, 3]，输出20，再比如数组为[1, -2, 3, 10, -4, 7, 2,
 * -5]，和最大的子数组为[3, 10, -4, 7, 2]，输出18。
 */
public class GetMaxOfArraySum {
    public static void main(String[] args) {
        //int[] array = {1, 4, -5, 9, 8, 3, -6};
        int[] array = {-1, -4, -5, -9, -8, -3, -6};
        //func1(array);
        //func1_1(array);
        //func2(array);
        func3(array);
    }

    /**
     * 暴力解法
     * 思路
     * 1、可以将给定数组的的所有子数组列出来，然后找到子数组和做大的情况，具体来说就是：
     *    对数组内每一个数A[i]进行遍历，然后遍历以它们为起点的子数组，比较各个子数组的大小，找到最大连续子数组；
     * 2、这种方法只是一般思路，时间复杂度太高，为：O(n^2)，不应该选择这样的方法。
     */
    public static void func1(int [] array) {
        int sum = -100000;//给定一个足够小的最大值
        for (int i = 0; i < array.length;i++){
            for (int j = 0; j < array.length; j++) {
                int subOfArr = 0;//临时最大值
                System.out.println(">i:"+i+" j:"+j);
                for (int k = i;k<=j;k++) {
                    System.out.println(">>k:"+k);
                    subOfArr += array[k];
                }
                if (subOfArr > sum) {
                    sum = subOfArr;
                }
            }
        }
        System.out.println("结果为："+sum);
    }

    /**
     * 方法func1演进
     * 上面的代码复杂度已经为n^3,在上面的代码基础上加以改进，使时间复杂度变为n^2
     * @param array
     */
    public static void func1_1(int[] array) {
        int sum = -100000;//给定一个足够小的最大值
        for (int i = 0; i < array.length;i++){
            int subOfArr = 0;//临时最大值
            for (int j = i; j < array.length; j++) {
                subOfArr += array[j];
                if (subOfArr > sum) {
                    sum = subOfArr;
                }
            }
        }
        System.out.println("结果为："+sum);
    }

    /**
     * 连续的最大的和 可能为 arr[ i -1 ]  + arr[ i ]
     * @param array
     */
    public static void func2(int[] array) {
        int sum = array[0];//临时最大
        int max = array[0];//比较后最大
        int arr[] = new int[array.length];
        for ( int i = 1; i < array.length; i++) {
            sum = maxTwoOfNum(sum+array[i], array[i]);
            if (sum > max) {
                arr[i] = array[i];
                max = sum;
            }
        }
        System.out.println("结果为："+max);
        System.out.println(Arrays.toString(arr));
    }

    public static int maxTwoOfNum(int a, int b) {
        return a > b ? a : b;
    }

    public static void func3(int[] array) {
        int max = array[0];
        int sum = array[0];
        for ( int i = 1; i< array.length; i++) {
            if ( sum < 0 ) {
                sum = array[i];
            } else {
                sum += array[i];
            }
            if (sum > max) {
                max = sum;
            }
        }
        System.out.println("结果为："+max);
    }
}
